This application discloses an algorithm suited for performing operation on hardware on Jacobian of a hyperelliptic curve defined over GF(2n). The following explains prerequisite knowledge required to understand the present invention.
[1] Hyperelliptic Curve and Divisor
There is a field referred to as K, and its algebraically closed field is referred to as K− (K with a bar on it). A hyperelliptic curve C of genus g over K is defined by an equation of the form: y2+h(x)y=f(x). Here, h(x) is a polynomial of a degree g at most, and f(x) is a monic polynomial of degree 2g+1. Here, polynomials f and g have coefficients in K and curve C has no singular points. Also, when rational point P=(x,y) is given, its opposite point is defined as {overscore (P)}=(x,−y−h(x)). If P is infinite-point P∞, it shall be P∞={overscore (P)}∞. Hereafter, this application assumes a case of filed K=GF(2n), h(x)=1.
A divisor D of C is a finite form sum of {overscore (K)}-points P1 . . . Pr and given by   D  =            ∑                        P          i                ∈        C              ⁢                  m        i            ⁢              P        i            
The degree of divisor D is defined by deg D=Σmi.       D    1    =            ∑                        P          i                ∈        C              ⁢                  m        i            ⁢              P        i                  D    2    =            ∑                        P          i                ∈        C              ⁢                  n        i            ⁢              P        i            
By defining the sum of divisors of C as             D      1        +          D      2        =            ∑                        P          i                ∈        C              ⁢                  (                              m            i                    +                      n            i                          )            ⁢              P        i            
D(C), a set of the entire divisors of C forms an additive group which is called a divisor group. The entire divisors of degree 0 from a subgroup which is denoted D0(C). The non zero rational function h of curve C has a finite number of zeros and poles, div(h) which is a divisor of h is defined by using zeros and poles of h in       div    ⁡          (      h      )        =                    ∑                              P            i                    ∈          C                    ⁢                                    ord                          P              i                                ⁡                      (            h            )                          ⁢                  P          i                      =                  ∑                              m            i                    ⁢                      P            i                              -              ∑                              n            i                    ⁢                      Q            i                              
Here, Pi is a zero of rational function h, mi is its multiplicity, Qi is a pole of rational function h, ni is multiplicity of poles, and ordPi (h) is an order of rational function h at point Pi. A divisor of a non zero rational function is called a principal divisor. A set of entire principal divisors is called a principal divisor group which is denoted D1(C).
In general, since the number of zeros and the number of poles of a rational function are equal if considered including multiplicity (order), it is D1(C)⊂D0(C). When two divisors D1 (Expression 1), D2 (Expression 2)εD0(C) are given, g.c.d. (D1,D2) of two divisors is defined by Σmin(mi,ni)Pi−(Σmin(mi,ni)P∞). Also, from the expression, it is apparently g.c.d. (D1,D2)⊂D0(C).
[2] Definition of Jacobian
Jacobian is defined to be the quotient group D0(C)/D1(C) about a group (see “Number Theory 2” by Yoshihiko Yamamoto, Iwanami Shoten (1996)). This is denoted as J(C). If D1,D2εD0(C) and D1−D2εD1(C), D1, D2 are called linearly equivalent. ∀DεD0(C) can be transformed to divisor D1(mi≧0) which satisfy the following conditions.       D    1    =                    ∑                              P            i                    ∈          C                    ⁢                        m          i                ⁢                  P          i                      -                  (                              ∑                                          P                i                            ∈              C                                ⁢                      m            i                          )            ⁢              P        ∞                (1) D1˜D    (2) If Pi appears in D1, then the point {overscore (P)}i does not appear as one of Pj(j≠i).    (3) When Pi={overscore (P)}, mi=1 at most.
Such a divisor is called a semi-reduced. An element of a Jacobian is uniquely represented by such a semi-reduced divisor subject to the additional condition that             ∑                        P          i                ∈        C              ⁢          m      i        ≤  g
Such a divisor is called a reduced divisor.
Any semi-reduced divisor D can be uniquely represented by D=g.c.d. ((a(x)), (y−b(x))). Here, a(x)=y−i(x−xi)mi and b(x) is the unique polynomial of degree<deg (a) satisfying b(xi)=yi. A necessary and sufficient condition for D to be a reduced divisor is deg a≦g. Hereafter, g.c.d. ((a(x)),(y−b(x))) is denoted as div(a,b) following “Computing in the Jacobian of a Hyperelliptic Curve,” D. G. Cantor, Math. Of Comp, 48, No. 177, pp. 95–101, (1987). In addition, divisor D is regarded as a pair of polynomials a and b hereafter.
The discrete logarithm problem on J(C;GF(2n)) is the problem of determining an integer m such that D1=mD2 for D1,D2εJ(C;GF(2n)).
[3] Security Conditions of Jacobian
The conditions which Jacobian J(C;GF(2n)) must satisfy in order to construct a secure hyperelliptic curve cryptosystem are as follows according to “Construction and Implementation of a Secure Hyperelliptic Curve CryptoSystem,” Yasuyuki Sakai, Yuichi Ishizuka and Kouichi Sakurai, SCIS'98–10.1.B, January, 1998, etc.    C1 #J(C;GF(2n)) is divisible by a large prime number.    C2 (2n)k−1, k<(log22)2 is indivisible by the largest prime factor of #J(C;GF(2n)).    C3 2g+1<log2n [4] Algorithm for Computing in Jacobian
Addition in Jacobian is, for D1,D2εJ(C;GF(2n)), to find a reduced divisor D′ which is a linearly equivalent to D1+D2. According to the aforementioned article of Cantor and, “Hyperelliptic Curve Cryptosystems,” N. Koblitz, Journal of Cryptology, 1, pp. 139–150, (1989), an algorithm for addition consists of two procedures. In this procedure 1, for input D1=div(a1,b1) and D2=div(a2,b2), semi-reduced divisor D is found, such that D1+D2 D (D=div(a,b)). In procedure 2, with this D as input, reduced divisor D′ is found, such that D˜D′ (D′=div(a′,b′), deg b′<deg a′, deg a′≦g). These procedures are as follows, if the hyperelliptic curve is y2+h(x)y=f(x).
Procedure 1
Inputa1, b1D1 = div(a1, b1)a2, b2D2 = div(a2, b2)Outputa, b    (1) s1(x), s2(x), s3(x) which satisfy d=s1a1+s2a2+s3(b1+b2+h) are calculated where a greatest common divisor (GCD) of polynomials a1(x), a2(x), b1(x)+b2(x)+h(x) is d=d(x).    (2) a(x), b(x) are calculated based on the following expression.a=a1a2/d2 b=(s1a1b2+s2a2b1+s3(b1b2+f))/d mod a Procedure 2
Inputa, bOutputa′, b′D to D′(1) a′(x) and b′(x) are calculated based on the following expression.
a′ = (f − hb − b2)/ab′ = (−h − b) mod a′(2) if (deg a′ > g) then  a = a′  b = b′  goto (1) else end
In particular, procedure 1 can be simplified as follows in the case of doubling.
Procedure 1a=a12 b=(b12+f)mod a go to procedure 2 (1).
If it is calculated as is with the above algorithm, there is a drawback that operation of a polynomial with a degree 2g becomes necessary leading to increased computation complexity.